package 代码随想录_回溯.力扣_回溯.回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * 这篇文章的思路好,代码好理解,具体写法根据代码随想录写法改写
 * https://leetcode.cn/problems/generate-parentheses/solutions/597236/sui-ran-bu-shi-zui-xiu-de-dan-zhi-shao-n-0yt3/?envType=study-plan-v2&envId=top-100-liked
 */
public class 括号生成_22 {
    List<String> res = new ArrayList<>();
    StringBuilder sb = new StringBuilder();
    public List generateParenthesis(int n) {
        dfs(n, 0, 0);
        return res;
    }

    private void dfs(int n, int left, int right) {
        //left,right分别代表左括号与右括号的数量，每生成一个我就增加一个
        if (right > left || right > n || left > n) {
            return;
        }
        if (left == n && right == n) {// 括号成对出现
            res.add(sb.toString());
            return;
        }
        // 回溯加左括号
        sb.append(')');
        dfs(n, left, right + 1);
        sb.deleteCharAt(sb.length() - 1);
        // 回溯加右括号
        sb.append('(');
        dfs(n, left + 1, right);
        sb.deleteCharAt(sb.length() - 1);
    }
}
